package com.example.demo.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/05 10:37
 */
public class _41_缺失的第一个正数 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 0};

        int[] nums1 = {3, 4, -1, 1, 9, -5};
        int i = firstMissingPositive3(nums1);
        System.out.println(i);
    }

    /**
     * 方法一：
     * 时间复杂度为O(n)
     * 空间复杂度为O(n)
     *
     * @param nums 数组
     * @return {@link int}
     * @author WangYX
     * @date 2024/03/05 10:56
     */
    public static int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (num > 0) {
                set.add(num);
            }
        }
        int min = 1;
        while (true) {
            if (!set.contains(min)) {
                return min;
            }
            min++;
        }
    }

    /**
     * 方法二：
     * 时间复杂度为O(n)
     * 空间复杂度为O(n)
     *
     * @param nums 数组
     * @return {@link int}
     * @author WangYX
     * @date 2024/03/05 10:56
     */
    public static int firstMissingPositive1(int[] nums) {
        int ans = 0;
        int len = nums.length;
        boolean[] hashTable = new boolean[len + 1];
        for (int num : nums) {
            if (num < 0 || num >= len + 1) {
                continue;
            }
            hashTable[num] = true;
        }
        for (int i = 1; i < len + 1; i++) {
            if (!hashTable[i]) {
                return i;
            }
        }
        return len + 1;
    }

    /**
     * 方法三：
     * 时间复杂度为O(n)
     * 空间复杂度为O(1)
     *
     * @param nums 数组
     * @return {@link int}
     * @author WangYX
     * @date 2024/03/05 11:18
     */
    public static int firstMissingPositive3(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
}
